import java.util.TreeSet;

/** The MemoryTree class is a uses a TreeSet of Memory to store free blocks of Memory.
 * The MemoryTree implements methods in the MemoryManager interface for allocating the smallest block of 
 * memory large enough to fulfil the request, deallocate a block of Memory by the Unique ID assigned to it,
 * defragment any contiguous blocks of free memory into one block and sort the Memory by starting Address
 * to facilitate the defragmentation. */
@SuppressWarnings("serial")
public class MemoryTree extends TreeSet<Memory> implements MemoryManager{

	private static int ID = 1;								// Unique ID assigned at each Allocation attempt 

	private SortingArray array;								//A SortingArray used to keep track of free memory
	private Memory[] usedMemory;							//An array of Memory where allocated memory is stored

	/** Returns the number of elements in this set (its cardinality). */
	public int getSize()
	{
		return size();
	}
	
	/** Constructor for the MemoryTree. Creates a new MemoryTree and inserts
	 * a block of free Memory of the specified size into the MemoryTree. 
	 * @param MemSize the total amount of memory alloted to the MemoryTree */
	public MemoryTree(int MemSize)
	{
		array = new SortingArray();							//creates the SortingArray
		usedMemory = new Memory[4];							//Creates an array to store used Memory

		add(new Memory(MemSize));							//adds the block of total Memory to the Tree
		array.insert(first());								//adds a reference of the total Memory to the Sorting Array
	}

	/** Attempts to allocate memory of the specified size. Finds the smallest block large enough
	 * to allocate from and returns the remaining amount of free memory to the MemoryTree. Returns
	 *  a String containting the UID of the transaction and the starting address if successful. 
	 *  If unsuccessful, then -1.
	 * @param size The amount of memory to allocate
	 * @return the ID and the address of the Memory as a String in the form "ID Address" */
	public String allocate(int size) 
	{
		Memory m = ceiling(new Memory(size));				//finds the smallest block large enough to allocate from or null if none exist

		while (ID >= usedMemory.length)						//Resizes the array of UsedMemory until large enough to fit the current ID
			usedMemory = resize(usedMemory);

		if (m == null) 										//If no suitable block is found, returns the ID and -1
			return ID++ + " " + -1;

		usedMemory[ID] = new Memory(size, m.address(), ID);	//Creates a block of the requested size and moves it to UsedMemory
		remove(m);											//removes the block being allocated out of from the MemoryTree
		array.remove(m.address());							//removes the block being allocated out of from the SortingArray

		if (m.size() - size != 0) {							//If there Memory leftover after allocation, returns is to the MemoryTree
			m = new Memory(m.size() - size, m.address()+size, -1);
			add(m);
			array.insert(m);
		}

		return ID + " " + usedMemory[ID++].address();		//Returns the ID of the transaction and the starting Address of the allocated block
	}

	/** Attempts to free the memory allocated at the Block with the designated UID. Returns a String stating whether
	 * the memory was successfully freed or not. 
	 * @param UID The unique ID number of the memory block
	 * @return "SUCCESS" if successful or "FAILED" otherwise */
	public String deallocate(int UID) 
	{	
		if(UID < 0 | UID >= usedMemory.length)
			return "FAILED";
		
			Memory m = usedMemory[UID];							//Locates the block in Used Memory by UID
		if (m == null)										//returns "FAILED" if the requested block was not found
			return "FAILED";

		//Returns the block to the MemoryTree and removes it from Used Memory 
		add(m);												
		array.insert(m);
		usedMemory[UID] = null;
		return "SUCCESS";
	}

	/** Attempts to partially defragment the Memory, merging any contiguous blocks into one block.
	 *  Clears the MemoryTree and inserts the new Memory blocks back into the Tree. Defrag is only called
	 *  after an unsuccessful allocation. */
	public void defrag() 
	{
		array = array.defrag();								//Sets the SortingArray as the defragmented SortingArray
		clear();											//clears the MemoryTree
		ID--;												//Decrements the ID so the following Allocate is assigned the proper ID

		for (Memory m : array) 								//Inserts each block of Memory in the SortingArray back into the Tree
			if (m != null)
				add(m);
	}

	/**	Sorts the Memory in the Sorting array by the starting Address so that they can be successfully merged
	 * by defrag(). First a quicksort is done on a copy of the SortingArray and then a Bucket Sort is performed on 
	 * the actual SortingArray. The times of these sorts are tracked and passed to the Statistics object.
	 * @param s The Statistics object that will get the time data of the sorts */
	public void sort(Statistics s) throws InterruptedException 
	{		
		array.quicksort(s);
		array.bucketsort(s);
	}

	/** Static method used to resize the array of UsedMemory in case the ID is greater than the bounds of the array 
	 * @param m	The array of Memory to be resized
	 * @return returns a reference to the resized array */
	private static Memory[] resize(Memory[] m) 
	{
		Memory[] temp = new Memory[m.length * 2];
		for (int i = 0; i < m.length; i++)
			temp[i] = m[i];
		return temp;		
	}
}
